package array.Binary_Search;
/*       给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
        完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
        不能使用任何内置的库函数，如  sqrt 。

        示例 1：
        输入：num = 16
        输出：true
        解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

        示例 2：
        输入：num = 14
        输出：false
        解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。*/
public class lc367 {
    public static void main(String[] args) {
        System.out.println(isPerfectSquare(808201));

    }
    public static boolean isPerfectSquare(int num) {
        int result=mySqrt2(num);
        if(num==result*result){
            return true;
        }else {
            return false;
        }

    }
    public  static int mySqrt2(int x) { //二分查找
        //可用二次不等式证明，当x>4时，根号x＜x/2
        //因此二分查找的右侧即为x/2
        //1-4的情况单独写出即可
        int low=0;
        int high=x/2;
        int mid=(low+high)/2;
        if(x==0){
            return 0;
        } else if(x>=1&&x<=3){
            return 1;
        } else if(x==4){
            return 2;
        }else {
            low=0;
            high=x/2;
            // mid=(low+high)/2;
            while(low<=high){
                mid = low + (high - low ) / 2;
                if(mid <= x / mid && (mid + 1) > x / (mid + 1)){   //写判断条件时，可使用÷代替×，避免越界
                    return mid;   //(mid < x / mid && (mid + 1) > x / (mid + 1))||mid ==x / mid
                } else if (x/mid<mid) {
                    high=mid-1;
                } else  {
                    low=mid+1;
                }
            }
            return 0;

        }


    }

}
